package com.ting.test.algorithms.大厂刷题班;

import com.ting.test.algorithms.二叉树.TreeNode;

/**
 * 找到A，b的最低公共祖先
 */

public class 最低公共祖先 {

    public static void main(String[] args) {
        TreeNode head = new TreeNode(2);
        TreeNode nodeA = new TreeNode(4);
        TreeNode nodeB = new TreeNode(2);
        final TreeNode node = process(head, nodeA, nodeB).node;

    }

    private static Info process(TreeNode treeNode, TreeNode nodeA, TreeNode nodeB) {
        if (treeNode == null) {
            return new Info(false, false, null);
        }

        Info left = process(treeNode.left, nodeA, nodeB);
        Info right = process(treeNode.right, nodeA, nodeB);

        TreeNode node = null;
        boolean findB = treeNode.getVal() == nodeB.getVal();
        boolean findA = treeNode.getVal() == nodeA.getVal();
        if (left != null) {
            findA = findA || left.findA;//如果
            findB = findB || left.findB;//如果
            node = left.node == null ? node : left.node;
        }

        if (right != null) {
            findA = findA || right.findA;//如果
            findB = findB || right.findB;//如果
            node = right.node == null ? node : right.node;

        }
        //如果a和b都找到了 并且节点为空 则表明当前就是公共
        if (findA && findB && node == null) {
            node = treeNode;
        }

        return new Info(findA, findB, node);

    }

    public static class Info {
        boolean findA;
        boolean findB;
        TreeNode node;

        public Info(boolean findA, boolean findB, TreeNode node) {
            this.findA = findA;
            this.findB = findB;
            this.node = node;
        }
    }
}
